/**
 * Implementation of a set of business process model measures, as presented in
 *   Jan Mendling. 2008. Metrics for Process Models: Empirical Foundations of 
 *   Verification, Error Prediction, and Guidelines for Correctness (1 ed.). 
 *   Springer Publishing Company, Incorporated. 
 * 
 * Copyright (c) 2010 Matthias Kunze
 * 
 * This software is licensed under the terms of Creative Commons Attribution-
 * NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0). 
 * 
 * You may share and remix this work, under the conditions that you 
 * - must attribute the work in the manner specified by the author or licensor
 * - may not use this work for any commercial purposes
 * - redistribute this work or any adaptations to it only under the same license to this one
 * 
 * For details, refer to the complete legal code of this license:
 * <http://creativecommons.org/licenses/by-nc-sa/3.0/legalcode>
 * 
 * Additional agreements to use this software can be granted by the author.
 * 
 * @author Matthias Kunze <mtkunze@gmail.com>
 * 
 * Currently supports following stencil sets
 * - BPMN2 (http://b3mn.org/stencilset/bpmn2.0#)
 * - EPC (http://b3mn.org/stencilset/epc#)
 * 
 */

package de.uni_potsdam.hpi.bpt.ai.util;

import java.util.Arrays;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import de.uni_potsdam.hpi.bpt.ai.diagram.Diagram;
import de.uni_potsdam.hpi.bpt.ai.diagram.Edge;
import de.uni_potsdam.hpi.bpt.ai.diagram.Node;
import de.uni_potsdam.hpi.bpt.ai.diagram.Shape;

public class BpmMetrics {

	/**
	 * contains all stencil shape ids that do not qualify as a control flow node
	 */
	protected static String[] nodeFilter = {
		// BPMN nodes that are not control flow nodes
		"Lane", "Group", "DataStore", "Pool", "TextAnnotation", 
		"DataObject", "CollapsedPool", "ITSystem", "processparticipant", "Message",
		
		// EPC nodes that are not control flow nodes
		"Organization", "TextNote", "Data", "Position", "System"
	};
	
	/**
	 * contains all stencil type ids that qualify as a control flow arc
	 */
	protected static String[] arcFilter = {
		// BPMN arcs that are control flow arcs
		"SequenceFlow", // "MessageFlow",
		
		// EPC arcs that are control flow arcs
		"ControlFlow"
	};
	
	/**
	 * contains all stencil type ids that qualify as and connector/parallel 
	 * gateway
	 */
	protected static String[] andConnectorFilter = {
		// BPMN connectors (gateways)
		"ComplexGateway", "ParallelGateway", "Task",
		// EPC connectors
		"AndConnector"
	};
	
	/**
	 * contains all stencil type ids that qualify as xor connector/exclusive 
	 * gateway
	 */
	protected static String[] xorConnectorFilter = {
		// BPMN connectors (gateways)
		"EventbasedGateway", "ComplexGateway", "Exclusive_Databased_Gateway", "Task", 
		
		// EPC connectors
		"XorConnector"
	};
	
	/**
	 * contains all stencil type ids that qualify as or connector/inclusive 
	 * gateways
	 */
	protected static String[]  orConnectorFilter = {
		// BPMN connectors (gateways)
		"InclusiveGateway", "ComplexGateway", 
		
		// EPC connectors
		"OrConnector"
	};
	
	
	/**
	 * Returns true if given shape is a control flow node
	 * 
	 * @param shape
	 * @return
	 */
	public static boolean isControlFlowNode(Shape shape) {
		for (String i : nodeFilter) {
			if (shape instanceof Node && i.equalsIgnoreCase(shape.getStencilId())) {
				return false;
			}
		}
		
		return true;
	}
	
	/**
	 * Returns true if given shape is a control flow node
	 * 
	 * @param shape
	 * @return
	 */
	public static Collection<Shape> filterControlFlowNodes(Collection<Shape> source) {
		Collection<Shape> target = new HashSet<Shape>();
		for (Shape s : source) {
			if (isControlFlowNode(s)) {
				target.add(s);
			}
		}
		return target;
	}
	
	/**
	 * Returns true if the given shape is a control flow arc
	 * 
	 * @param shape
	 * @return
	 */
	public static boolean isControlFlowArc(Shape shape) {
		for (String i : arcFilter) {
			if (shape instanceof Edge && i.equalsIgnoreCase(shape.getStencilId())) {
				return true;
			}
		}
		return false;
	}
	
	public static Collection<Shape> filterControlFlowArcs(Collection<Shape> source) {
		Collection<Shape> target = new HashSet<Shape>();
		for (Shape s : source) {
			if (isControlFlowArc(s)) {
				target.add(s);
			}
		}
		return target;
	}
	
	/**
	 * Returns true if the given shape is a connector/gateway
	 * 
	 * @param stencilId
	 * @return
	 */
	protected static boolean isConnector(String stencilId) {
		if (null == connectors) {
			connectors = new HashSet<String>();
			connectors.addAll(Arrays.asList(andConnectorFilter));
			connectors.addAll(Arrays.asList(xorConnectorFilter));
			connectors.addAll(Arrays.asList(orConnectorFilter));
		}
		
		for (String i : connectors) {
			if (i.equalsIgnoreCase(stencilId)) {
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Returns true if the given shape is a connector/gateway
	 * 
	 * @param shape
	 * @return
	 */
	protected static boolean isConnector(Shape shape) {
		return isConnector(shape.getStencilId());
	}
	protected static Set<String> connectors = null;
	
	/**
	 * Returns true a node has no incoming control flow arc and thus is a start 
	 * node.
	 * 
	 * @param node
	 * @return
	 */
	protected static boolean isStartNode(Node node) {
		if (!isControlFlowNode(node)) {
			return false;
		}
		
		int in = 0;
		for (Shape shape : node.getIncomings()) {
			if (isControlFlowArc(shape)) {
				in++;
			}
		}
		
		return 0 == in;
	}
	
	/**
	 * Extracts all edges from a the child shapes of a shape
	 * 
	 * @param shape
	 * @return
	 */
	protected Set<Edge> getEdges(Shape shape) {
		Set<Edge> edges = new HashSet<Edge>();
		
		for(Shape child : shape.getChildShapes()) {
			if (child instanceof Edge) {
				edges.add((Edge)child);
			}
			
			edges.addAll(getEdges(child));
		}
		return edges;
	}
	
	/**
	 * Extracts all nodes from a the childshapes of a shape
	 * 
	 * @param shape
	 * @return
	 */
	protected static Set<Node> getNodes(Shape shape) {
		Set<Node> nodes = new HashSet<Node>();
		
		for(Shape child : shape.getChildShapes()) {
			if (child instanceof Node) {
				nodes.add((Node)child);
			}
			
			nodes.addAll(getNodes(child));
		}
		return nodes;
	}
	
	
	/**
	 * Number of control flow nodes of a process model graph.
	 * @param diagram
	 * @return
	 */
	public static long size(Shape diagram) {
		long nodes = 0;
		
		for (Shape shape : diagram.getChildShapes()) {
			if (shape instanceof Node) {
				if (isControlFlowNode(shape)) {
					nodes++;
				}
				
				nodes = nodes + size(shape);
			}
		}
		
		return nodes;
	}
 
	
	/**
	 * Number of fully connected control flow arcs of a process model graph.
	 * 
	 * @param shape
	 * @return
	 */
	public static long sizeArcs(Shape shape) {
		long arcs = 0;
		
		for (Shape child : shape.getChildShapes()) {
			if ((child instanceof Edge) && isControlFlowArc(child) && child.getIncomings().size() > 0 && child.getOutgoings().size() > 0) {
				arcs++;
			}
			
			arcs += sizeArcs(child);
		}
		
		return arcs;
	}
	
	
	/**
	 * The diameter gives the length of the longest path from a start node to an
	 * end node in the process model.
	 * The length of a path is represented by the number of nodes it contains.
	 * 
	 * @param diagram
	 * @return
	 */
	public static long diameter(Shape diagram) {
		return diameter(diagram, new HashSet<Shape>());
	}
	
	/**
	 * Returns the number of edges and nodes of the longest path
	 * 
	 * @param diagram diagram or container node
	 * @param visited shapes that have been visited during inspection, to avoid 
	 *        infinite paths with loops
	 * @return
	 */
	protected static long diameter(Shape diagram, Set<Shape> visited) {
		
		long diameter = 0;

		for (Shape shape : diagram.getChildShapes()) {
			
			visited.add(shape);
			
			// start edges (i.e. not connected to start nodes) shall not be 
			// ignored as they may lead to start nodes
			if (shape instanceof Edge && isControlFlowArc(shape)) {
				for (Shape out : shape.getOutgoings()) {
					if (out instanceof Node && isStartNode((Node) out)) {
						
						Set<Shape> path = new HashSet<Shape>(visited);
						diameter = Math.max(diameter, longestPathFrom((Node)out, path));
					}
				}
			}
			else if (shape instanceof Node && isStartNode((Node) shape)) {
				
				Set<Shape> path = new HashSet<Shape>(visited);
				diameter = Math.max(diameter, longestPathFrom((Node)shape, path));
			}
			
			// recurse
			diameter = Math.max(diameter, diameter(shape, new HashSet<Shape>(visited)));
		}
		
		return diameter;
	}
	
	/**
	 * Iteratively calculates the longest path from a shape to the end of the
	 * diagram
	 * 
	 * @param shape current shape
	 * @param visited shapes that have been visited during inspection, to avoid
	 *        infinite paths with loops
	 * @return
	 */
	protected static long longestPathFrom(Node node, Set<Shape> visited) {
		long pathSize = 0;
		
		if (0 < node.getChildShapes().size()) {
			Set<Shape> path = new HashSet<Shape>(visited);
			pathSize = diameter(node, path);
		}
		
		for (Shape edge : node.getOutgoings()) {
			if (isControlFlowArc(edge)) {
				for (Shape succ : edge.getOutgoings()) {
					if (succ instanceof Node && isControlFlowNode(succ) && !visited.contains(succ)) {
						visited.add(succ);
						pathSize = Math.max(pathSize, longestPathFrom((Node) succ, new HashSet<Shape>(visited)));
					}
				}
				
				
			}
		}
		return pathSize + 1;
	}
	
	/**
	 * The density of the process graph refers to the number of arcs divided by
	 * the number of the maximum number of arcs for the same number of nodes.
	 * 
	 * @param diagram
	 * @return
	 */
	public static double density(Shape diagram) {
		double nodes = (double) size(diagram);
		double arcs = (double) sizeArcs(diagram);
		
		if (1 >= nodes) {
			return 0;
		}
		
		return arcs / (nodes*(nodes-1));
	}
	
	/**
	 * The coefficient of connectivity gives the ratio of arcs to nodes.
	 * 
	 * @param diagram
	 * @return
	 */
	public static double cnc(Shape diagram) {
		double nodes = (double) size(diagram);
		double arcs = (double) sizeArcs(diagram);
		
		if (0 == nodes) {
			return 0;
		}
		
		return arcs / nodes;
	}
	
	/**
	 * Returns the maximum number of incoming and outgoing shapes of a shape 
	 * If shape is a node, returns the max number of incoming/outgoing edges,
	 * otherwise returns number of incoming/outgoing nodes.
	 * 
	 * @param shape
	 * @return
	 */
	public static double degree(Node shape) {
		return Math.max(
				filterControlFlowArcs(shape.getIncomings()).size(), 
				filterControlFlowArcs(shape.getOutgoings()).size());
	}
	
	/**
	 * The average degree of connectors gives the number of nodes a connector
	 * is in average connected to.
	 * 
	 * @param diagram
	 * @return
	 */
	public static double avgDc(Shape diagram) {
		return avgDegree(getConnectors(diagram));
	}
	
	/**
	 * Calculates the average degree (max number of incoming/outgoing shapes) 
	 * of a given set of shapes
	 * 
	 * @param shapes
	 * @return
	 */
	public static double avgDegree(Set<Node> shapes) {
		if (0 == shapes.size()) {
			return 0;
		}
		
		double sum = 0;
		for (Node shape : shapes) {
			sum += degree(shape);
		}
		
		if (0 == shapes.size()) {
			return 0;
		}
		
		
		return sum/(double)shapes.size();
	}
	
	/**
	 * The maximum degree of all connectors
	 * 
	 * @param diagram
	 * @return
	 */
	public static double maxDc(Shape diagram) {
		return maxDegree(getConnectors(diagram));
	}
	
	/**
	 * Calculates the maximum degree (max number of incoming/outgoing shapes) 
	 * of a given set of shapes
	 *  
	 * @param dcs the collection of connectors 
 	 * @return
	 */
	public static double maxDegree(Set<Node> shapes) {
		if (0 == shapes.size()) {
			return 0;
		}
		
		double max = 0;
		for (Node shape : shapes) {
			max = Math.max(max, degree(shape));
		}
		return max;
	}
	
	/**
	 * Returns the set of all connectors in a diagram.
	 * 
	 * @param shape
	 * @return
	 */
	protected static Set<Node> getConnectors(Shape shape) {
		Set<Node> dc = new HashSet<Node>();
		
		for (Shape child : shape.getChildShapes()) {			
			if (child instanceof Node && isConnector(child)) {
				dc.add((Node)child);
			}
			
			dc.addAll(getConnectors(child));
		}
		
		return dc;
	}
	
	/**
	 * Cyclicity relates nodes on a cycle to the number of nodes.
	 * 
	 * @param diagram
	 * @return
	 */
	public static double cyc(Shape diagram) {
		Set<Node> nodes = getNodes(diagram);
		int loopNodes = 0;
		TransitiveClosure tc = new TransitiveClosure(diagram);
		
		for (Node node : nodes) {
			if (tc.isInLoop(node)) {
				loopNodes ++;
			}
		}
		
		if (0 == nodes.size()) {
			return 0;
		}
		
		return (double)loopNodes / (double)nodes.size();
	}
	
	
	/**
	 * The token split sums up the output degree of AND-joins and OR-joins minus
	 * one. (A measure for concurrency.)
	 * 
	 * @param diagram
	 * @return
	 */
	public static int ts(Shape diagram) {
		Set<String> connectorTypes = new HashSet<String>(Arrays.asList(andConnectorFilter));
		connectorTypes.addAll(Arrays.asList(orConnectorFilter));
		
		int ts = 0;
		for (Shape shape : diagram.getChildShapes()) {
			if ((shape instanceof Node)) {
				for (String i : connectorTypes) {
					if (i.equalsIgnoreCase(shape.getStencilId())) {
						int out = filterControlFlowArcs(shape.getOutgoings()).size();
						// only count connectors that split tokens 
						ts += (out > 1 ? (out - 1) : 0);
					}
				}
			}
			
			ts += ts(shape);
		}
		
		return ts;
	}
	
	/**
	 * The connector heterogeneity gives the entropy over the different 
	 * connector types.
	 * 
	 * @param diagram
	 * @return
	 */
	public static double ch(Diagram diagram) {
		
		Map<String, Integer> connectorCount = new HashMap<String, Integer>();
		int connectorTypeCount = 0;
		
		// how many connector types does the stencil set have (diagram may have)
		for (String sid : diagram.getStencilset().getStencils()) {
			if (isConnector(sid)) {
				connectorTypeCount++;
			}
		}
		
		// how many connectors of the respective type have been used
		countConnectors(diagram, connectorCount);
		
		// how many connectors have been found in the diagram at all
		double numberOfConnectors = 0;
		for (int i : connectorCount.values()) {
			numberOfConnectors += i;
		}
		
		double ch = 0;
		for (int c : connectorCount.values()) {
			// sum_{l \in connectory-types}{(|C_l| / |C|) * log_{3}(|C_l| / |C|)
			ch += ((double)c / numberOfConnectors) *  (Math.log((double)c / numberOfConnectors) / Math.log(connectorTypeCount));
		}
		
		return -1 * ch;
	}
	
	/**
	 * counts connectors of different types
	 * 
	 * @param shape 
	 * @param connectorCount stores current statistics of connectors (count per 
	 *        type)
	 */
	protected static void countConnectors(Shape shape, Map<String, Integer> connectorCount) {
		for (Shape child : shape.getChildShapes()) {
			if (child instanceof Node) {
				String sId = child.getStencilId();				
				
				// count only real connectors that are used as such (avoid counting SESE tasks in BPMN)
				if (isConnector(sId) && (filterControlFlowArcs(child.getOutgoings()).size() > 1 || filterControlFlowArcs(child.getIncomings()).size() > 1)) {
					if (connectorCount.containsKey(sId)) {

						connectorCount.put(sId, connectorCount.get(sId) + 1);
					}
					connectorCount.put(sId, 1);
				}
			}
			
			// recursion
			countConnectors(child, connectorCount);
		}
	}
}